home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / SimulationMultiplexor.cc,v < prev    next >
Text File  |  1989-02-22  |  12KB  |  551 lines
  1. head     3.2;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    grunwald:3.2; strict;
  6. comment  @@;
  7.  
  8.  
  9. 3.2
  10. date     89.02.20.15.37.25;  author grunwald;  state Exp;
  11. branches ;
  12. next     3.1;
  13.  
  14. 3.1
  15. date     88.12.20.13.49.15;  author grunwald;  state Exp;
  16. branches ;
  17. next     1.1;
  18.  
  19. 1.1
  20. date     88.10.30.13.03.23;  author grunwald;  state Exp;
  21. branches ;
  22. next     ;
  23.  
  24.  
  25. desc
  26. @@
  27.  
  28.  
  29. 3.2
  30. log
  31. @Start using Gnu library heaps for schedulers
  32. @
  33. text
  34. @// This may look like C code, but it is really -*- C++ -*-
  35. // 
  36. // Copyright (C) 1988 University of Illinois, Urbana, Illinois
  37. //
  38. // written by Dirk Grunwald (grunwald@@cs.uiuc.edu)
  39. //
  40. #include "SimulationMultiplexor.h"
  41. #include "SpinLock.h"
  42. #include "SpinBarrier.h"
  43. #include "SpinFetchAndOp.h"
  44. #include "AwesimeHeap.h"
  45. #include "Thread.h"
  46.  
  47. #include "TimeSchedulerSplayPQ.h"
  48.  
  49. #include "ReserveByException.h"
  50. #include <math.h>
  51.  
  52. SimulationMultiplexor *ThisSimulationMultiplexor;
  53. static SpinBarrier CpuBarrier(0);
  54.  
  55. //
  56. //    The PendingEvents queue is private to each processor
  57. //
  58.  
  59.   static TimeSchedulerPQ *PendingEvents[MaxCpuMultiplexors];
  60.  
  61. static SpinLock PendingEventsLock[MaxCpuMultiplexors];
  62.  
  63. double CurrentSimulatedTime = 0.0;
  64.  
  65. extern int CpuMuxDebugFlag;
  66.  
  67. SimulationMultiplexor::SimulationMultiplexor(int debug, int spinMax)
  68.     : (debug)
  69. {
  70.     pNameTemplate = "SimMux";
  71.     cpuBarrier = &CpuBarrier;
  72.     CpuBarrier.maxLoops(spinMax);
  73.     ThisSimulationMultiplexor = this;
  74.     ThisCpu = this;
  75.     allocateLocalEventStructures(0,1);
  76.     sprintf(nameSpace, "[%s-%d] ", pNameTemplate, iYam);
  77.     pName = nameSpace;
  78. }
  79.  
  80. SimulationMultiplexor::~SimulationMultiplexor()
  81. {
  82. }
  83.  
  84. void
  85. SimulationMultiplexor::allocateLocalEventStructures(int newIYam, int outOf)
  86. {
  87. #ifndef NDEBUG
  88.     if (CpuMuxDebugFlag) {
  89.     CpuCerrLock.reserve();
  90.     cerr << name() << "Allocate SimMux structures for " << newIYam << "\n";
  91.     CpuCerrLock.release();
  92.     }
  93. #endif /* NDEBUG */
  94.  
  95.     PendingEvents[newIYam] = new TimeSchedulerSplayPQ;
  96.  
  97.     myPendingEvents = PendingEvents[newIYam];
  98.     myPendingEventsLock = &PendingEventsLock[newIYam];
  99.  
  100. #ifndef NDEBUG
  101.     if (CpuMuxDebugFlag) {
  102.     CpuCerrLock.reserve();
  103.     cerr << name() << "set CpuBarrier height to " << outOf << "\n";
  104.     CpuCerrLock.release();
  105.     }
  106. #endif /* NDEBUG */
  107.     CpuBarrier.height( outOf );
  108. }
  109.  
  110. void
  111. SimulationMultiplexor::allocateEventStructures(int newIYam, int outOf)
  112. {
  113.     allocateLocalEventStructures(newIYam, outOf);
  114.  
  115.     //
  116.     // must do this after the local structures get set up so that
  117.     // CpuMultiplexors does not increase until all data structures are
  118.     // in place, otherwise people may poke at them before they're set up.
  119.     //
  120.  
  121.     CpuMultiplexor::allocateEventStructures(newIYam, outOf);
  122. }
  123.  
  124. void
  125. SimulationMultiplexor::deallocateEventStructures()
  126. {
  127.  
  128.     CpuMultiplexor::deallocateEventStructures();
  129.  
  130. #ifndef NDEBUG
  131.     if (CpuMuxDebugFlag) {
  132.     CpuCerrLock.reserve();
  133.     cerr << name() << "Deallocate SimMux structures for" << iYam << "\n";
  134.     CpuCerrLock.release();
  135.     }
  136. #endif /* NDEBUG */
  137.  
  138.     PendingEventsLock[0].reserve();
  139.  
  140.     while ( ! myPendingEvents -> empty() ) {
  141.     assert( iYam != 0 );
  142.     TimeScheduler& item = myPendingEvents -> front();
  143.     PendingEvents[0] -> enq( item );
  144.     myPendingEvents -> del_front();
  145.     }
  146.  
  147.     PendingEventsLock[0].release();
  148.  
  149.     delete myPendingEvents;
  150.     myPendingEvents = 0;
  151.     PendingEvents[iYam] = 0;
  152.  
  153. #ifndef NDEBUG
  154.     if (CpuMuxDebugFlag) {
  155.     CpuCerrLock.reserve();
  156.     cerr << name() << "set CpuBarrier height to " << CpuMultiplexors << "\n";
  157.     CpuCerrLock.release();
  158.     }
  159. #endif /* NDEBUG */
  160.     CpuBarrier.height(CpuMultiplexors);
  161. }
  162.  
  163. void
  164. SimulationMultiplexor::warmThePot(int cpus)
  165. {
  166.     
  167.     if ( cpus > MaxCpuMultiplexors ) {
  168.     cpus = MaxCpuMultiplexors;
  169.     }
  170.  
  171.     CpuBarrier.height(cpus);
  172.     CpuMultiplexor::warmThePot(cpus);
  173.     int ok = CpuBarrier.rendezvous();
  174. #ifndef NDEBUG
  175.     if (! ok ) {
  176.     CpuCerrLock.reserve();
  177.     cerr << name() << "barrier overrun\n";
  178.     CpuCerrLock.release();
  179.     }
  180. #endif
  181. }
  182.  
  183. void
  184. SimulationMultiplexor::stirItAround()
  185. {
  186.     while( ! *terminated ) {
  187.     CpuMultiplexor::stirItAround();
  188.     if (! *terminated ) {
  189.         advanceTime();
  190.     }
  191.     }
  192. }
  193.  
  194. void
  195. SimulationMultiplexor::coolItDown()
  196. {
  197.     CpuBarrier.rendezvous();
  198.     CpuMultiplexor::coolItDown();
  199.     //
  200.     //  In case we call rendezvous again
  201.     //
  202.     CpuBarrier.height(CpuMultiplexors);
  203. }
  204.  
  205. void
  206. SimulationMultiplexor::addAt(Thread *who, double when)
  207. {
  208.     if (when <= CurrentSimulatedTime) {
  209.     add(who);
  210.     }
  211.     else {
  212. #ifndef NDEBUG
  213.     if (CpuMuxDebugFlag) {
  214.         CpuCerrLock.reserve();
  215.         cerr << name() << " add " << who -> name() << " to pending\n";
  216.         CpuCerrLock.release();
  217.     }
  218. #endif /* NDEBUG */
  219.     //
  220.     // Add them to pending events
  221.     //
  222.     myPendingEvents->enq( TimeScheduler(who, when) );
  223.     }
  224. }
  225.  
  226. void
  227. SimulationMultiplexor::addWithDelay(Thread *who, double delay)
  228. {
  229.     delay += CurrentSimulatedTime;
  230.     addAt(who, delay);
  231. }
  232.  
  233. //
  234. //    Advance time. Assumes all other CPUs are idle, so no locking
  235. //    on event structures is needed.
  236. //
  237. int
  238. SimulationMultiplexor::advanceTime()
  239. {
  240.     //
  241.     //    If, for some reason, we fail to rendezvous after the timeout,
  242.     //  click on debug output.
  243.     //
  244.  
  245.     int ok = CpuBarrier.rendezvous();
  246.  
  247. #ifndef NDEBUG
  248.     if ( !ok ) {
  249.     int oldFlag = CpuMuxDebugFlag;
  250.  
  251.     CpuMuxDebugFlag = 1;
  252.     CpuCerrLock.reserve();
  253.     cerr << name() << "rendezvous fails, enable debugging\n";
  254.     CpuCerrLock.release();
  255.     while ( ! CpuBarrier.rendezvous() );
  256.  
  257.     CpuMuxDebugFlag = oldFlag;
  258.     CpuCerrLock.reserve();
  259.     cerr << name() << "rendezvous resumes, reset debugging\n";
  260.     CpuCerrLock.release();
  261.     }
  262. #endif /* NDEBUG */
  263.  
  264.     
  265.     //
  266.     // Nothing is locked at this point.
  267.     //
  268.     
  269.     if (iYam == 0) {
  270. #ifndef NDEBUG
  271.     if (CpuMuxDebugFlag) {
  272.         CpuCerrLock.reserve();
  273.         cerr << name() << "Scan " << CpuMultiplexors << " for pending\n";
  274.         CpuCerrLock.release();
  275.     }
  276. #endif /* NDEBUG */
  277.     
  278.     //
  279.     // Find the minimum time over all pending event piles
  280.     //
  281.     double when = MAXFLOAT;
  282.     bool validItem = FALSE;
  283.     for (int i = 0; i < CpuMultiplexors; i++ ) {
  284.         TimeSchedulerPQ *p = PendingEvents[i];
  285.         if ( ! p -> empty() ) {
  286.         double hapAt = (p -> front()).time();
  287.         if (hapAt < when) {
  288.             when = hapAt;
  289.             validItem = TRUE;
  290.         }
  291.  
  292. #ifndef NDEBUG
  293.         if (CpuMuxDebugFlag) {
  294.             CpuCerrLock.reserve();
  295.             cerr << name() << i;
  296.             cerr << " has one at " << hapAt << "\n";
  297.             CpuCerrLock.release();
  298.         }
  299. #endif /* NDEBUG */
  300.         }
  301. #ifndef NDEBUG
  302.         else {
  303.         if (CpuMuxDebugFlag) {
  304.             CpuCerrLock.reserve();
  305.             cerr << name() << i << " has nothing\n";
  306.             CpuCerrLock.release();
  307.         }
  308.         }
  309. #endif /* NDEBUG */
  310.     }
  311.     
  312.     if ( !validItem ) {
  313. #ifndef NDEBUG
  314.         if (CpuMuxDebugFlag) {
  315.         CpuCerrLock.reserve();
  316.         cerr << name() << " Unable to advance time, exit \n";
  317.         CpuCerrLock.release();
  318.         }
  319. #endif /* NDEBUG */
  320.         *terminated = 1;
  321.     }
  322.     else {
  323.         
  324. #ifndef NDEBUG
  325.         if (CpuMuxDebugFlag) {
  326.         CpuCerrLock.reserve();
  327.         cerr << name() << " ADVANCE TIME TO " << when << "\n" ;
  328.         CpuCerrLock.release();
  329.         }
  330. #endif /* NDEBUG */
  331.         
  332.         assert( CurrentSimulatedTime <= when );
  333.         CurrentSimulatedTime = when;
  334.     }
  335.     }
  336.     
  337.     CpuBarrier.rendezvous();
  338.     
  339.     //
  340.     // Now that we know the time of the minimum entry in the
  341.     // heap, remove all the events which occur at that time
  342.     // or before that time (actually, that is an error).
  343.     //
  344.     // Each process does its own work to reduce overhead.
  345.     // We keep track of how many processes were added to
  346.     // the current events queue and then bump the global
  347.     // events count by that amout.
  348.     //
  349.     // This cannot cause race conditions because we only
  350.     // use this info in the rendevzous to advance time
  351.     // code above, and not all cpus will be there yet
  352.     // (i.e. the current cpu is not there)
  353.     //
  354.     ThreadContainer *c = myCurrentEvents;
  355.     int added = 0;
  356.     
  357.     myCurrentEventsLock -> reserve();
  358.  
  359.     TimeSchedulerPQ *p = myPendingEvents;
  360.     while ( ! p -> empty() ) {
  361.     TimeScheduler &item = p -> front();
  362.     if ( item.time() > CurrentSimulatedTime )
  363.         break;
  364.     addUnlocked( item.thread() );
  365.     added++;
  366.     p -> del_front();
  367.     } 
  368.     
  369.     *myCurrentEventsCounter += added;
  370.     myCurrentEventsLock -> release();
  371.  
  372.     globalCurrentEventsCounter -> add(added);
  373.     
  374. #ifndef NDEBUG
  375.     if ( CpuMuxDebugFlag ) {
  376.     CpuCerrLock.reserve();
  377.     cerr << name() << " added " << added << " threads to current";
  378.     cerr << ", leaving me " << myPendingEvents -> length() << "\n";
  379.     CpuCerrLock.release();
  380.     }
  381. #endif
  382.     return(added);
  383. }
  384.  
  385. void
  386. SimulationMultiplexor::await(double when)
  387. {
  388.     if (when > CurrentSimulatedTime) {
  389.     addAt( currentThread, when );
  390.     Thread *next = CpuMultiplexor::remove();
  391.     if ( next == 0 ) {
  392.         raise( &iveSuspendedException );
  393.     } else {
  394.         Thread *from = currentThread;
  395.         currentThread = next;
  396. #ifndef NDEBUG
  397.         if (CpuMuxDebugFlag) {
  398.         CpuCerrLock.reserve();
  399.         cerr << name() << " switch to " << currentThread -> name() << "\n";
  400.         CpuCerrLock.release();
  401.         }
  402. #endif    /* NDEBUG */
  403.         from -> pContext.switchContext ( &(currentThread -> pContext) );
  404.     }
  405.     }
  406. }
  407.  
  408. void
  409. SimulationMultiplexor::hold(double holdFor)
  410. {
  411.     if (holdFor > 0) {
  412.     await( CurrentSimulatedTime + holdFor );
  413.     }
  414. }
  415. @
  416.  
  417.  
  418. 3.1
  419. log
  420. @Steay version
  421. @
  422. text
  423. @d13 3
  424. a15 1
  425. #include "HeapScheduler.h"
  426. d26 2
  427. a27 1
  428. static AwesimeHeap *PendingEvents[MaxCpuMultiplexors];
  429. d62 2
  430. a63 1
  431.     PendingEvents[newIYam] = new AwesimeHeap(128);
  432. d107 1
  433. a107 1
  434.     while ( ! myPendingEvents -> isEmpty() ) {
  435. d109 3
  436. a111 4
  437.     AwesimeHeapItem item;
  438.     if (myPendingEvents -> remove(item)) {
  439.         PendingEvents[0] -> add( item );
  440.     }
  441. d113 1
  442. d189 1
  443. a189 1
  444.     myPendingEvents->add( AwesimeHeapItem(when, who) );
  445. d251 3
  446. a253 3
  447.         AwesimeHeap *p = PendingEvents[i];
  448.         if ( ! p -> isEmpty() ) {
  449.         double hapAt = p -> item( p -> minItem() ).key();
  450. d258 1
  451. a320 2
  452.     AwesimeHeapItem item;
  453.     AwesimeHeap *p = myPendingEvents;
  454. d326 6
  455. a331 9
  456.     for (AwesimeHeapIndex index = p -> minItem();
  457.      index != AwesimeHeapNull
  458.      && p -> item(index).key() <= CurrentSimulatedTime;
  459.      index = p -> minItem() )
  460.     {
  461.     bool removed = p -> remove(item);
  462.     assert( removed );
  463.     Thread * who = (Thread *) item.ptr();
  464.     addUnlocked( who );
  465. d333 2
  466. a334 1
  467.     }
  468. d345 1
  469. a345 1
  470.     cerr << ", leaving me " << myPendingEvents -> size() << "\n";
  471. @
  472.  
  473.  
  474. 1.1
  475. log
  476. @Initial revision
  477. @
  478. text
  479. @d31 1
  480. a31 1
  481. SimulationMultiplexor::SimulationMultiplexor(int debug)
  482. d34 1
  483. a34 1
  484.     allocateEventStructures(0);
  485. d36 1
  486. d39 3
  487. d49 1
  488. a49 1
  489. SimulationMultiplexor::allocateEventStructures(int newIYam)
  490. d51 7
  491. a57 3
  492.     CpuMultiplexor::allocateEventStructures(newIYam);
  493.     sprintf(nameSpace, "[SimulationMultiplexor-%d] ", iYam);
  494.     pName = nameSpace;
  495. d59 12
  496. a70 3
  497.     PendingEvents[iYam] = new AwesimeHeap(128);
  498.     myPendingEvents = PendingEvents[iYam];
  499.     myPendingEventsLock = &PendingEventsLock[iYam];
  500. d74 14
  501. d90 1
  502. d93 8
  503. d110 1
  504. a111 1
  505.     PendingEventsLock[0].release();
  506. d115 9
  507. d136 8
  508. a143 1
  509.     CpuBarrier.rendezvous();
  510. d149 1
  511. a149 2
  512.     while( ! *terminated )
  513.     {
  514. d151 2
  515. a152 5
  516. #ifndef NDEBUG
  517.     if (CpuMuxDebugFlag) {
  518.         CpuCerrLock.reserve();
  519.         cerr << name() << "Finished with current batch, advance time\n";
  520.         CpuCerrLock.release();
  521. a153 2
  522. #endif /*NDEBUG*/
  523.     advanceTime();
  524. d203 24
  525. a227 2
  526.     CpuBarrier.rendezvous();
  527.     
  528. d236 1
  529. a236 1
  530.         cerr << name() << "rendezvous to advance time\n";
  531. d254 8
  532. d263 9
  533. d275 7
  534. a298 7
  535.     //
  536.     // Why the second rendezvous?
  537.     // If tasks are priority ordered, we want to be able
  538.     // to pull them out, order them & then start.
  539.     //
  540.     // Also, advance time depends on this.
  541.     //
  542. d311 1
  543. a311 1
  544.     // This canot cause race conditions because we only
  545. d337 1
  546. d343 2
  547. a344 1
  548.     cerr << name() << " added " << added << " threads to current\n";
  549. d371 8
  550. @
  551.